import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 207. 课程表
 */
public class Solution_207 {
    /**
     * 拓扑排序 广度优先搜索
     * <p>
     * 时间复杂度：O(N+M)，遍历一个图需要访问所有节点和所有临边，N 和 M 分别为节点数量和临边数量
     * <p>
     * 空间复杂度：O(N+M)，为建立邻接表所需额外空间，adjacency 长度为 N，并存储 M 条临边的数据
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 入度表
        int[] indegrees = new int[numCourses];
        // 邻接表
        List<List<Integer>> adjacency = new ArrayList<>();
        // 队列中存放「入度为 0」的节点
        Queue<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        // 得到每个节点的入度和邻接表
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        // 得到所有「入度为 0」的节点，并将其入队
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        // BFS 拓扑排序
        while (!queue.isEmpty()) {
            // 在每次 pre 出队时，执行 numCourses-1
            int pre = queue.poll();
            numCourses--;
            for (int cur : adjacency.get(pre)) {
                // 将此节点对应所有邻接节点（它指向的结点） cur 的入度 -1
                indegrees[cur]--;
                // 如果入度 -1 后邻接节点 cur 的入度为 0，
                // 说明 cur 所有的前驱节点已经被“删除”，此时将 cur 入队。
                if (indegrees[cur] == 0) {
                    queue.add(cur);
                }
            }
        }
        return numCourses == 0;
    }

    public static void main(String[] args) {
        Solution_207 solution = new Solution_207();
        // 测试 1
        int numCourses = 5;
        int[][] prerequisites = { { 4, 3 }, { 4, 2 }, { 3, 1 }, { 3, 0 }, { 2, 1 }, { 1, 0 } };
        boolean ans = solution.canFinish(numCourses, prerequisites);
        System.out.println(ans);
        // 测试 2
        numCourses = 2;
        prerequisites = new int[][] { { 1, 0 }, { 0, 1 } };
        ans = solution.canFinish(numCourses, prerequisites);
        System.out.println(ans);
    }
}
